/*
 * Thread em busy waiting: fica sempre verificando se o limite foi trocado
 */

#include <pthread.h>
#include <unistd.h>
#include <sys/types.h>

#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

string palavra1, palavra2;
int linhas, colunas;
int *matriz;
int *vetor;
pthread_mutex_t *m1;


int position(int linha, int coluna) {
    int p = linha * colunas + coluna;
    return p;
}

void insert(int* shm, int x, int linha, int coluna) {
    int p = position(linha, coluna);
    shm[p] = x;
}

int get(int* shm, int linha, int coluna) {
    int p = position(linha, coluna);
    return shm[p];
}

void lock(pthread_mutex_t* m) {
    pthread_mutex_lock(m);
}

void unlock(pthread_mutex_t* m) {
    pthread_mutex_unlock(m);
}

void print(int* shm) {
    cout << "  ";
    for (int j = 0; j < colunas; j++) {
        cout << palavra1[j] << " ";
    }
    cout << endl;

    for (int i = 0; i < linhas; i++) {
        cout << palavra2[i] << " ";
        for (int j = 0; j < colunas; j++) {
            cout << get(shm, i, j) << " ";
        }
        cout << endl;
    }
}

void *run(void *num) {
    
    int id;
    memcpy(&id, &num, sizeof(int));
    int linha = id;
    int coluna;
    int limite;
    int coluna_atual = 1;
    
    while (coluna_atual < colunas) {
        // le seu limite de uma thread (de linha == linha-1)
        lock(&m1[linha-1]);
        limite = vetor[linha-1];
        unlock(&m1[linha-1]);
        
        // executa o algoritmo
        for (coluna = coluna_atual; coluna <= limite; coluna++) {
            if (coluna == 0) {
                break;
            }
            
            if (coluna == colunas) {
                lock(&m1[linha]);
                vetor[linha] = colunas;
                unlock(&m1[linha]);
                break;
            }
            
            char char_linha = palavra2[linha];
            char char_coluna = palavra1[coluna];

            if (char_linha == char_coluna) {
                int res = get(matriz, linha - 1, coluna - 1);
                insert(matriz, res + 1, linha, coluna);
            }
            else {
                int res = max(get(matriz, linha, coluna - 1), get(matriz, linha - 1, coluna));
                insert(matriz, res, linha, coluna);
            }

            // escreve seu limite para que uma thread (de linha == linha+1) possa ler
            lock(&m1[linha]);
            vetor[linha] = coluna;
            unlock(&m1[linha]);
        }
        coluna_atual = limite;
    }
    
    pthread_exit(NULL);
}

int main() {
    int size;
    pthread_t *threads;
    int linha, coluna;

    // palavras
    cout << "Digite a primeira palavra: ";
    cin >> palavra1;
    palavra1 = '$' + palavra1;
    colunas = palavra1.size();

    cout << "Digite a segunda palavra: ";
    cin >> palavra2;
    palavra2 = '$' + palavra2;
    linhas = palavra2.size();

    // tamanho da regiao de memoria
    size = linhas * colunas;
    
    // criacao da matriz da PD, do vetor (que será compartilhado) e das threads; semaforos binários
    vetor = new int[linhas];
    threads = new pthread_t[linhas];
    matriz = new int[size];

    m1 = new pthread_mutex_t[linhas];

    // inicializa a matriz de resposta
    for (linha = 0; linha < linhas; linha++) {
        insert(matriz, 0, linha, 0);
    }

    for (coluna = 0; coluna < colunas; coluna++) {
        insert(matriz, 0, 0, coluna);
    }
    
    // inicializa o vetor
    for (linha = 0; linha < linhas; linha++) {
        vetor[linha] = 1;
    }
    vetor[0] = colunas;

    // cria os mutex
    for (int i=0; i < linhas; i++) {
        pthread_mutex_init(&m1[i], NULL);
    }

    // cria as threads
    for (int i=1; i < linhas; i++) {
        pthread_create(&threads[i], NULL, run, (void *) i);
    }

    for (int i=1; i < linhas; i++) {
        pthread_join(threads[i], NULL);
    }

    // codigo que o pai executa depois que todos os filho terminam
    cout << endl;
    print(matriz);

    string palavra = "";
    linha = linhas - 1;
    coluna = colunas - 1;

    while (get(matriz, linha, coluna) != 0) {
        if (get(matriz, linha-1, coluna) == get(matriz, linha, coluna)) {
            linha -= 1;
        }    
        else {
            palavra = palavra2[linha] + palavra;
            linha -= 1;
            coluna -= 1; 
        }
    }
    cout << "Resposta: " << palavra << endl;

    return 0;
}
